数据结构 Hash 相关知识

什么是 Hash

Hash 也称散列、哈希，对应的英文都是 Hash。基本原理就是把任意长度的输入，通过 Hash 算法变成固定长度的输出。这个映射的规则就是对应的 Hash 算法，而原始数据映射后的二进制串就是哈希值。常见的有SHA1、SHA256、MD5、TIGER等等，它们采用不同的一些算法来实现这个功能，不同的 Hash 算法得到的结果也不一定相同，但是同一个 Hash 算法对指定内容的结果必须相同。

注意：不要把散列函数和散列技术弄混，散列技术既是一种存储方法，也是一种查找方法。它与线性表、树、图等结构不同，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向査找的存储结构。

在开始学习前先理解如下几个定义：

如果散列表中存在和散列原始输入 K 相等的记录，那么 K 必定在 $f(K)$ 的存储位置上
不同关键字经过散列算法变换后可能得到同一个散列地址，这种现象称为碰撞
如果两个 Hash 值不同（前提是同一 Hash 算法），那么这两个 Hash 值对应的原始输入必定不同

所以一个优秀的 Hash 算法就有如下几个特点

从 Hash 值不可以反向推导出原始的数据
输入数据的微小变化会得到完全不同的 Hash 值，相同的数据会得到相同的值
哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
Hash 算法的冲突概率要小
散列地址分布均匀

散列函数

最简单的散列函数就是：除留余数法

f( key ) = key mod p ( p ≤ m )

也可在折叠、平方取中后再取模

例如：15 % 2 = 1

就可以计算出这个数为 1，同理 111 % 15 = 10 就可以计算出这个数为 10

除留余数法例子

有一个关键字，它有 12 个记录，现在我们要针对它设计一个散列表。如果采用除留余数法，那么可以先尝试将散列函数设计为 f(key) = key mod 12 的方法。比如 29 mod 12 = 5，所以它存储在下标为 5 的位置。

不过这也是存在冲突的可能的，因为 12 = 2×6 = 3×4。如果关键字中有像 18(3×6)、30(5×6)、42(7×6) 等数字，它们的余数都为 6，这就和 78 所对应的下标位置冲突了。

但是如果不选用 p=12 来做除留余数法，而选用 p=11，这个时候就只有 12 和 144 有冲突，相对来说，就要好很多了。所以需要挑选一个好的 P

如何合理选取 p 值

使用除留余数法的一个经验是，若散列表表长为 m，通常 p 为小于或等于表长（最好接近 m）的最小质数或不包含小于 20 质因子的合数。例如某散列表的长度为 100，散列函数 H(k) = k % P，则选择 97做为 P

哈希表的优势与劣势

参考资料 HashMap实现原理及源码分析

前面说了这么多，那这个哈希表有什么好处呢，在说这个哈希表好处前先来看下其它的数据结构在新增和查找等操作的性能

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为 $O(1)$ ；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为 $O(n)$ ,当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为 $O(logn)$ ；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为 $O(n)$

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为 $O(1)$ ,而查找操作需要遍历链表逐一进行比对，复杂度为 $O(n)$

二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为 $O(logn)$ 。

哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为 $O(1)$

综上，哈希表的速度还是很快的，因此散列技术最适合的场景是需要快速插入数据和求解问题是査找与给定值相等的记录。对于査找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。

比如那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术。一个班级几十个学生，他们的性别有男有女，你用关键字 “男” 去査找，对应的有许多学生的记录，这显然是不合适的。这个时候可以用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。

同样散列表也不适合范围查找，比如査找一个班级18-22岁的同学，在散列表中没法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。

如何计算 hash？

hash 是如何计算出来的？

看源码，发现基本每个插入函数都调用了两个方法 hash(Object key)、indexFor(int h, int length)

int hash = hash(key); // 对 key 的 hashcode 进一步计算，确保散列均匀
int i = indexFor(hash, table.length);// 获取在 table 中的实际位置

先来看这个 indexFor 方法，它是用来计算出元素具体是存在 table 哪里

/**
 * 返回数组下标
 */
static int indexFor(int h, int length) {
    // 实际上相当于 h % length 取余数，但&计算速度更快，具体为什么使用 & 不使用 % 看下面那个为什么是 2 的次幂那一节
    return h & (length-1); 
}

理论上散列值是一个 int 型，如果直接拿散列值作为下标访问 HashMap 主数组的话，考虑到 2 进制 32 位带符号的 int 表值范围从 -2147483648 ~ 2147483648。前后加起来大概 40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但问题是一个 40亿长度的数组，内存是放不下的。HashMap 扩容之前的数组初始大小才 16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。所以就需要使用到这个 indexFor 方法了

“与” 操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2进制表示是 00000000 00000000 00001111 和某散列值做 “与” 操作如下，结果就是截取了最低的四位值。

    10100101 11000100 00100101
&   00000000 00000000 00001111
----------------------------------
    00000000 00000000 00000101    //高位全部归零，只保留末四位

*这也正好解释了为什么 HashMap 的数组长度要取 2 的整次幂：hashMap 的数组长度一定保持 2 的次幂，比如 16 的二进制表示为 10000，那么 length-1 就是 15，二进制为 01111，同理扩容后的数组长度为 32，二进制表示为 100000，length-1 为 31，二进制表示为 011111。这样会保证低位全为 1*（这里搭配下面那个为什么是 2 的次幂那节使用）

为什么需要使用 “扰动函数”

上面看着只采用 hashCode，也能取得 table 里面的位置啊为什么还需要执行 hash 方法取得一个新的 hashCode？

因为上面调用的是 Object 里面的 hashCode 取得的散列码，所以为了防止一些实现比较差的 hashCode() 方法，使用扰动函数之后可以减少碰撞，进一步降低 hash 冲突的几率。

打个比方，当我们的数组长度 n 为 16 的时候，哈希码（字符串 “abcabcabcabcabc” 的 key 对应的哈希码）对 16-1 与操作，对于多个 key 生成的 hashCode，只要哈希码的后 4 位为 0，不论不论高位怎么变化，最终的结果均为0。如下表所示

对象	二进制码
1954974080（HashCode）	111 0100 1000 0110 1000 1001 1000 0000
2^4-1=15（length-1）	000 0000 0000 0000 0000 0000 0000 1111
&运算	000 0000 0000 0000 0000 0000 0000 0000

所以就需要使用 “扰动函数” 对原 HashCode 进行扰动

// 这里是 JDK8的
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

右位移 16位，正好是 32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。（如下流程图）

回到上面的例子，加上高 16位异或低 16位的“扰动函数”后，结果如下：

对象	转换成十进制	二进制码
原HashCode	1954974080	111 0100 1000 0110 1000 1001 1000 0000
(>>>16)无符号右移16位	29830	000 0000 0000 0000 0111 0100 1000 0110
^（异或）运算	1955003654	111 0100 1000 0110 1111 1101 0000 0110
2^4-1=15（length-1）	15	000 0000 0000 0000 0000 0000 0000 1111
&（与）运算	6	000 0000 0000 0000 0000 0000 0000 0110

可以看到 “扰动” 之后，高低位互换后，就能极大的减少碰撞

Hash 碰撞的解决方案

前面提到了 Hash 算法是一定会有冲突的（因为分配的内存不是无限大的，为了优化内存的肯定会出现 Hash 碰撞的情况），那么如果遇到了 Hash 冲突比较常用的算法是链地址法和开放地址法。

链地址法

参考资料 HashMap实现原理及源码分析

链表地址法是使用一个链表数组，来存储相应数据，当 Hash 遇到冲突的时候依次添加到链表的后面进行处理。

链地址在处理的流程如下：添加一个元素的时候，首先计算元素 key 的 Hash 值，确定插入数组中的位置。如果当前位置下没有重复数据，则直接添加到当前位置。当遇到冲突的时候，添加到同一个 Hash 值的元素后面，行成一个链表。这个链表的特点是同一个链表上的 Hash 值相同。

Java 的数据结构 HashMap 使用的就是这种方法来处理冲突，JDK1.8 中，针对链表上的数据超过 8 条的时候，使用了红黑树进行优化。

开放地址法

参考资料散列冲突处理：开放定址法

开放地址法是指大小为 M 的数组保存 N 个键值对，其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为 “开放地址” 哈希表。（所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。）

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。

线性探测法（ThreadLocalMap），就是比较常用的一种 “开放地址” 哈希表的一种实现方式。

公式为：

fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
m：memory

比如说，我们的关键字集合为 {12,67,56,16,25,37,22,29,15,47,48,34} ，表长为12。使用的散列函数为： f(key) = key % 12（一般不可能这么简单）

当计算前 5 个数 {12,67,56,16,25} 时，都是没有冲突的散列地址，直接存入：

下标	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25	空	空	16	空	空	67	56	空	空	空

计算 key = 37 时，发现 f(37) = 1，此时就与25所在的位置冲突。

于是我们应用上面的公式 f(37) = (f(37)+1) mod 12 = 2。于是将 37 存入下标为 2 的位置。

下标	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25	37	空	16	空	空	67	56	空	空	空

接下来 22,29,15,47 都没有冲突，正常的存入：

下标	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25	37	15	16	29	空	67	56	空	22	47

到了 key = 48，我们计算得到 f(48) = 0，与 12 所在的 0 位置冲突了，不要紧，我们 f(48) = (f(48)+1) mod 12 = 1，此时又与 25 所在的位置冲突。于是 f(48) = (f(48)+2) mod 12=2，还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6 时，才有空位

下标	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25	37	15	16	29	48	67	56	空	22	47

Java 中的 HashCode

HashCode 优化 Set插入

参考资料 Java面试——HashCode的作用原理和实例解析

Java 中的集合有两类，一类是 List，再有一类是 Set。前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。 equals 方法可用于保证元素不重复，但如果每增加一个元素就检查一次，若集合中现在已经有 1000 个元素，那么第 1001 个元素加入集合时，就要调用 1000 次 equals 方法。这显然会大大降低效率。于是，HashSet 采用了哈希表的原理。（注意：HashSet 内部就是使用的 HashMap）

哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。这样一来，当集合要添加新的元素时，先调用这个元素的 HashCode 方法，就一下子能定位到它应该放置的物理位置上。

如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；
如果这个位置上已经有元素了，就调用它的 equals 方法与新元素进行比较，相同的话就不存了；
不相同的话，也就是发生了 Hash key 相同导致冲突的情况，那么就在这个 Hash key 的地方产生一个链表，将所有产生相同 HashCode 的对象放到这个单链表上去，串在一起。这样一来实际调用 equals 方法的次数就大大降低了，几乎只需要一两次。

从 Object 角度看，JVM 每 new 一个 Object，它都会将这个 Object 丢到一个 Hash 表中去，这样的话，下次做 Object 的比较或者取这个对象的时候（读取过程），它会根据对象的 HashCode 再从 Hash 表中取这个对象。这样做的目的是提高取对象的效率。若 HashCode 相同再去调用 equal

为何要重写 HashCode 方法

为什么重写 Object 的 equals(Object obj) 方法尽量要重写 Object 的 HashCode() 方法？

前面说了 Set 是先通过比对对象的 HashCode 来判断这些对象是否是同一个，所以如果不重写 HashCode 会导致相同的对象（内部数据相同）得到的 HashCode 也不同，从而导致 Set 里面存在重复的元素

// 自己定义一个 HashCodeClass 不重写 HashCode 方法
public class HashCodeClass {
    private String str0;
    private double dou0;
    private int    int0;

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof HashCodeClass) {
            HashCodeClass hcc = (HashCodeClass)obj;

            if (hcc.str0.equals(this.str0) &&
                hcc.dou0 == this.dou0 &&
                hcc.int0 == this.int0) {
                return true;
            }
            return false;
        }
        return false;
    }
}

如果不重写 HashCode() 那每个对象输出的 HashCode 都是不同的

public class TestMain {
    public static void main(String[] args) {
        System.out.println(new HashCodeClass().HashCode());
        System.out.println(new HashCodeClass().HashCode());
        System.out.println(new HashCodeClass().HashCode());
        System.out.println(new HashCodeClass().HashCode());
        System.out.println(new HashCodeClass().HashCode());
        System.out.println(new HashCodeClass().HashCode());
    }
}
// 如上，实例化后未赋值，按理它们应该是相同的，但是输出的 HashCode 却不相同
1901116749
1807500377
355165777
1414159026
1569228633
778966024

上面的 HashCodeClass 都没有赋初值，那么这 6 个 HashCodeClass 应该是全部相同的。

所以应该加上这个

@Override
public int hashCode() {
    return Objects.hash(str0, dou0, int0);
}

HashMap 实现原理

参考资料 HashMap实现原理及源码分析

HashMap 内部结构

注意：HashMap 的实现在 JDK7和8 有点不同，下面也会指出它们的区别

HashMap 的主干是一个 Entry 数组（哈希桶数组）。Entry 是 HashMap 的基本组成单元（JDK8 改名为 Node了），每一个 Entry 包含一个 key-value 键值对。

// HashMap 的主干数组，可以看到就是一个 Node 数组，初始值为空数组{}
transient Node<K,V>[] table;

主干数组的长度一定是 2 的次幂

在讲这个数组前先来看下这个 Node 对象是啥

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //对 key 的 hashcode 值进行 hash 运算后得到的值，存储在 Entry，避免重复计算
    final K key;
    V value;
    Node<K,V> next; // 存储指向下一个Entry的引用，单链表结构

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    /* ... */
}

JDK7 的 HashMap 由一个 Node 数组和链表组成

所以 HashMap 的整体结构为如下这样

HashMap 由数组 + 链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（具体看上面的链地址法），如果定位到的数组位置不含链表（当前 entry 的 next 指向 null）,那么对于查找，添加等操作很快，仅需一次寻址即可；

如果定位到的数组包含链表（Hash 碰撞了），对于添加操作，其时间复杂度为 $O(n)$ ,首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过 key 对象的 equals 方法逐一比对查找。

所以，性能考虑 HashMap 中的链表出现越少，性能才会越好。（这个就要看 Hash 算法的性能了）

JDK8 使用Node 数组加链表\红黑树构成

在 JDK8 中，当链表长度大于 8 时转为红黑树存储，基本结构如下：

这么做主要是再查询的时间复杂度上进行优化，链表为 $O(n)$ ,而红黑树一直是 $O(logn)$ ,当 Hash碰撞超过 8个时，可以大大的提高查找性能。

如何初始化 HashMap

先来看几个重要的字段，在初始化 HashMap 时会用到这些字段

// 实际存储的 key-value 键值对的个数
transient int size;

/**
 * threshold 就是阈值，当 table == {} 时，该值为初始容量（初始容量默认为16）；当 table 被填充了，
 * 也就是为 table 分配内存空间后，threshold 一般为 capacity*loadFactory。 
 * HashMap 在进行扩容时需要参考 threshold
 */
int threshold;

// 负载因子，代表了 table 的填充度有多少，默认是 0.75
final float loadFactor;

/**
 * 用于快速失败，由于 HashMap 非线程安全，在对 HashMap 进行迭代时，
 * 如果期间其他线程的参与导致 HashMap 的结构发生变化了（比如put，remove等操作），
 * 需要抛出异常 ConcurrentModificationException 
 */
transient int modCount;

HashMap 有 4个构造器，其他构造器如果用户没有传入 initialCapacity（初始容量）和 loadFactor 这两个参数，会使用默认值，初始容量为 16，loadFactor 为 0.75

public HashMap() {
    // 这个 DEFAULT_LOAD_FACTOR 为 0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

如果手动构建一个 HashMap 还是有所限制的（这里使用 JDK8 的代码）

// 此处对传入的初始容量进行校验，最大不能超过 MAXIMUM_CAPACITY = 1<<30(230)
public HashMap(int initialCapacity, float loadFactor) {
    // 健壮性判断
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;
    // JDK7 中这里的 this.threshold = initialCapacity；分配两倍大小的幂是放在 put初始化那里执行的
    this.threshold = tableSizeFor(initialCapacity);
}

// 对于给定的目标容量，返回两倍大小的幂。
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

如果没有手动指定初始容量，那数组 table 只有在第一个 put 方法调用时才会被构建，所以接下去看下面的 put 方法

如何添加一个元素

JDK8 之后因为当冲突大于 8之后会转成红黑树，所以这部分 put 方法有点复杂，所以这里直接看 JDK7版的。只要知道 JDK8 会变成红黑树就行了

public V put(K key, V value) {
    // 如果 table 数组为空数组 {}，进行数组填充（为 table 分配实际内存空间），
    // 入参为 threshold，此时 threshold 为 initialCapacity 默认是 1<<4(24=16)
    if (table == EMPTY_TABLE) {
        inflateTable(threshold); 
    }

    // 如果 key 为 null，存储位置为 table[0] 或 table[0] 的冲突链上
    if (key == null)
        return putForNullKey(value);

    int hash = hash(key); // 对 key 的 hashcode 进一步计算，确保散列均匀
    int i = indexFor(hash, table.length);// 获取在 table 中的实际位置

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    // 如果该对应数据已存在，执行覆盖操作。用新 value 替换旧 value，并返回旧 value
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;// 保证并发访问时，若 HashMap 内部结构发生变化，快速响应失败
    addEntry(hash, key, value, i);// 新增一个 entry
    return null;
}

这里的 inflateTable 方法如下，用于为 table 分配空间

private void inflateTable(int toSize) {
    // 通过 roundUpToPowerOf2(toSize) 可以确保 capacity 为大于或等于 toSize 的最接近 toSize 的二次幂，
    // 比如 toSize=13,则 capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
    int capacity = roundUpToPowerOf2(toSize);
    // //此处为 threshold 赋值，取 capacity*loadFactor 和 MAXIMUM_CAPACITY+1 的最小值，
    // capacity 一定不会超过 MAXIMUM_CAPACITY，除非 loadFactor 大于 1
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

/**
 * roundUpToPowerOf2 中的这段处理使得数组长度一定为 2 的次幂，
 * Integer.highestOneBit 是用来获取最左边的 bit（其他 bit 位为0）所代表的数值.
 */
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

下面是 JDK8 详细的插入操作，因为有点长，不感兴趣直接跳到下一部分

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果存储元素的table为空，则进行必要字段的初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 获取长度
        n = (tab = resize()).length;
    // 如果根据hash值获取的结点为空，则新建一个结点
    // 此处 & 代替了 % （除法散列法进行散列）
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 这里的p结点是根据hash值算出来对应在数组中的元素
    else {
        Node<K,V> e; K k;
        // 如果新插入的结点和table中p结点的hash值，key值相同的话
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树结点的话，进行红黑树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // 代表这个单链表只有一个头部结点，则直接新建一个结点即可
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度大于8时，将链表转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 及时更新p
                p = e;
            }
        }
        // 如果存在这个映射就覆盖
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 判断是否允许覆盖，并且value是否为空
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 回调以允许LinkedHashMap后置操作
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 更改操作次数
    ++modCount;
    // 大于临界值
    if (++size > threshold)
        // 将数组大小设置为原来的2倍，并将原先的数组中的元素放到新数组中
        // 因为有链表，红黑树之类，因此还要调整他们
        resize();
    // 回调以允许LinkedHashMap后置操作
    afterNodeInsertion(evict);
    return null;
}

为什么是 2 的次幂

参考资料为什么HashMap的长度是2的整数次幂？ - tqz的文章 - 知乎

为何 HashMap 的数组长度一定是 2 的次幂？

为了加快哈希计算以及减少哈希冲突，那为什么可以加快计算？

都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算 hash(KEY) % 数组长度

但是！% 计算比 & 慢很多

所以用 & 代替 %，为了保证 & 的计算结果等于 % 的结果需要把 length 减 1

也就是 hash(KEY) & (length - 1)

这个 hash(KEY) 上面已经介绍了，调用 Object 里面的 native 方法完成计算，一般返回的是一个整数，至于是偶数还是奇数就不一定了

假设现在数组的长度：2 ^ 14 = 16384

String key = "zZ1!." 的 hash 值为 115398910

public static void main(String[] args) {
        String key = "zZ1!.";
        System.out.println(key.hashCode());// 115398910
}

下面使用 & 代替 % 尝试：

hash & (length - 1) = 115398910 & 16383 = 6398 ，而 6398 的二进制是 ‭0001100011111110‬
hash % length = 115398910 % 16384 = 6398

结果确实一样，但是 & 运算更快！

还有一个有意思的事就是：因为扩容为 2 的倍数，根据 hash 桶的计算方法，元素哈希值不变而通过 % 计算的方式会因为 length 的变化导致计算出来的 hash 桶的位置不断变化。数据一致在漂移，影响性能！！

那为什么可以减少冲突？

假设现在数组的长度 length 可能是偶数也可能是奇数，length 为偶数时：length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。

例如 length = 4，length - 1 = 3， 3 的 二进制是 11
若此时的 hash 是 2，也就是 10，那么 10 & 11 = 10（偶数位置）
hash = 3，即 11 & 11 = 11 （奇数位置）

而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 hash & (length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间

length = 3， 3 - 1 = 2，他的二进制是 10
10 无论与什么数进行 & 运算，结果都是偶数

因此，length 取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中 均匀地散列。

哈希桶数组如何扩容

参考资料 JDK8中的HashMap初始化和扩容机制

这里直接讲 JDK8的扩容方法

前面说过，这个 table 默认才分配 16个位置，随着元素的增加，这明显不够

看 JDK8的 put方法，它会在大于临界值时执行 resize 方法扩容，这个临界值默认是 0.75f，即当元素大于这个数据的 75% 时执行扩容方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /* ... */

    // 大于临界值
    if (++size > threshold)
        // 将数组大小设置为原来的 2 倍，并将原先的数组中的元素放到新数组中
        // 因为有链表，红黑树之类，因此还要调整他们
        resize();
    // 回调以允许 LinkedHashMap 后置操作
    afterNodeInsertion(evict);
    return null;
}

下面就直接来看这个扩容方法的源码（看注释）

// 初始化或者扩容之后元素调整
final Node<K,V>[] resize() {
    // 获取旧元素数组的各种信息
    Node<K,V>[] oldTab = table;
    // 长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容的临界值
    int oldThr = threshold;
    // 定义新数组的长度及扩容的临界值
    int newCap, newThr = 0;

    // 如果原 table 不为空
    if (oldCap > 0) {
        // 如果数组长度达到最大值，则修改临界值为 Integer.MAX_VALUE
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 下面就是扩容操作（2倍）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // threshold 也变为二倍
            newThr = oldThr << 1; // double threshold
    }
    // 原 table 为 0，表示要初始化数组
    else if (oldThr > 0) // 初始容量设置为阈值（JDK8 里这个阈值是计算过的，一般默认是 16）
        newCap = oldThr;
    // threshold为 0，则使用默认值
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 如果临界值还为0，则设置临界值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    // 更新填充因子
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 调整数组大小之后，需要调整红黑树或者链表的指向
    if (oldTab != null) {
        
        // 遍历旧数组，将原有 Node数组的元素拷贝到新的 Node数组里
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            
            // 重新计算元素在新数组中的位置
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 红黑树调整
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 链表调整
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap 什么时候会扩容

当 HashMap 中元素总个数达到阈值时就会扩容。注意是元素总个数，而不是数组占用个数。

// 数组扩容阈值，即：HashMap 数组总容量 * 负载因子
int threshold
// 如果元素个数大于阈值，扩充数组。 
if (++size > threshold)  
    resize();

TODO: 扩容细节之后再补充

Reference

参考资料为什么HashMap的长度是2的整数次幂？ - tqz的文章 - 知乎参考资料讲讲HashCode的作用参考资料 Java面试——HashCode的作用原理和实例解析参考资料深入理解Hash和HashCode的应用参考资料散列表是怎么进行查找的？参考资料散列函数设计：直接定址法参考资料 JDK 源码中 HashMap 的 hash 方法原理是什么？ - 胖君的回答参考资料使用位操作（&运算）代替求余操作参考资料 HashMap中确定数组位置为什么要用hash进行扰动

什么是 Hash​

散列函数​

除留余数法例子​

如何合理选取 p 值​

哈希表的优势与劣势​

如何计算 hash？​

为什么需要使用 “扰动函数”​

Hash 碰撞的解决方案​

链地址法​

开放地址法​

Java 中的 HashCode​

HashCode 优化 Set插入​

为何要重写 HashCode 方法​

HashMap 实现原理​

HashMap 内部结构​

如何初始化 HashMap​

如何添加一个元素​

为什么是 2 的次幂​

哈希桶数组如何扩容​

HashMap 什么时候会扩容​

Reference​

什么是 Hash

散列函数

除留余数法例子

如何合理选取 p 值

哈希表的优势与劣势

如何计算 hash？

为什么需要使用 “扰动函数”

Hash 碰撞的解决方案

链地址法

开放地址法

Java 中的 HashCode

HashCode 优化 Set插入

为何要重写 HashCode 方法

HashMap 实现原理

HashMap 内部结构

如何初始化 HashMap

如何添加一个元素

为什么是 2 的次幂

哈希桶数组如何扩容

HashMap 什么时候会扩容

Reference